package Count;
import java.util.Collections;
import java.util.ArrayList;
import java.util.*;

//给你一个单词列表判断前k个出现次数最多的单词是什么？
public class Words {
    public static List<String> Frequent(String[] words ,int k){
        HashMap<String,Integer> map=new HashMap<>();
        for(String word:words){
            if(map.get(word)==null){
                map.put(word,1);
            }else{
                int val=map.get(word);
                map.put(word,val+1);
            }
        }
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(
                new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        if(o1.getValue().compareTo(o2.getValue())==0){
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());
                    }
                }
        );
        for (Map.Entry<String,Integer> entry:map.entrySet()){
            if(minHeap.size()<k){
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top=minHeap.peek();
                if(top.getValue().compareTo(entry.getValue())<0){
                    minHeap.poll();
                    minHeap.offer(entry);
                } else if (top.getValue().compareTo(entry.getValue())==0) {
                    if(top.getKey().compareTo(entry.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        ArrayList<String> List=new ArrayList<>();
        for(int i=0;i<k;i++){
            Map.Entry<String,Integer> tmp=minHeap.poll();
            List.add(tmp.getKey());
        }
        Collections.reverse(List);
        return List;
    }
    public static void main(String[] args){
        String [] words={"i","love","love","i","a","a","king","leetcode"};
        int k=3;
        List<String> r=Frequent(words,k);
        System.out.println(words+"中前"+k+"个高频单词："+r);
    }
}
